package 回溯.不熟;

import java.util.ArrayList;
import java.util.List;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 格雷编码89.java
 * @createTime 2023年01月07日 14:10:00
 */
public class 格雷编码89 {
	List<Integer> res = new ArrayList<>();
	public List<Integer> grayCode(int n) {
		backtrace(n,new StringBuffer(),new int[]{0,1});
		return res;
	}
	public void backtrace(int n, StringBuffer sb, int[] nums){
		//判断条件，是否返回
		if(sb.length() == n){
			// 二进制转换为十进制
			res.add(Integer.valueOf(sb.toString(),2));
			return;
		}
		// 回溯第一个状态
		sb.append(nums[0]);
		//注意数组
		backtrace(n,sb,new int[]{0,1});
		sb.deleteCharAt(sb.length()-1);
		// 回溯第二个状态
		sb.append(nums[1]);
		//注意数组
		backtrace(n,sb,new int[]{1,0});
		sb.deleteCharAt(sb.length()-1);
	}
}
